package com.bascker.algorithm.practice.sliding_window.middle.find_repeated_dna_sequences;

import java.util.ArrayList;
import java.util.List;

/**
 * TTL
 */
public class Solution1 {

    // 0 <= s.len
    public List<String> findRepeatedDnaSequences(String s) {
        // 处理非法数据
        if (null == s || s.length() < 10) {
            return new ArrayList<>();
        }

        int n = s.length();

        final List<String> rs = new ArrayList<>();
        // 给定2个指针 l,r, 指针闭区间 [l, r] 控制距离 10，即滑动窗口大小 = 10
        int l = 0;
        int r = 9;

        while (l < n && r < n) {
            // 每得到一个子串，判断其是否在原串中有重复
            String sub = s.substring(l, r + 1);
            boolean isRepeat = isRepeat(s, sub);

            // 若有，则将子串加入结果集，l + 1, r + 1
            if (isRepeat && !rs.contains(sub)) {
                rs.add(sub);
            }

            // 若没有，则 l + 1, r + 1
            l ++;
            r ++;
        }

        return rs;
    }

    private boolean isRepeat(String src, String sub) {
        int count = 0;
        for (int i = 0; i < src.length(); i++) {
            if (i + 10 > src.length()) {
                break;
            }

            // 注意：substring 是左闭右开区间，因此这里要加10
            String s = src.substring(i, i + 10);
            if (s.equals(sub)) {
                count ++;
            }
        }

        return count > 1;
    }

}
